#include "BTreeNode.h"

using namespace std;

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read(pid, buffer);
}
 
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  int keyCount = 0;
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    if (buffer[i] != '\0')
      keyCount++;
    else
      return keyCount;
  }
  return keyCount;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
  // Error out if the node is full
  if(getKeyCount() == 85)
    return RC_NODE_FULL;

  // Find the first entry that is equal to or greater than the key
  int index;
  RC rc = locate(key, index);

  // Convert the pid, sid, and key into cstrings
  char cpid[5];
  sprintf(cpid, "%04d", rid.pid);
  char csid[5];
  sprintf(csid, "%04d", rid.sid);
  char ckey[5];
  sprintf(ckey, "%04d", key);
  
  // Insert the (key, rid) pair at the end
  if (rc == RC_NO_SUCH_RECORD)
  {
    strncpy(&buffer[index * 12    ], cpid, 4);
    strncpy(&buffer[index * 12 + 4], csid, 4);
    strncpy(&buffer[index * 12 + 8], ckey, 4);
    return 0;
  }

  // Insert the key in the middle
  // First split into two where the insertion point should be
  char firstHalf[PageFile::PAGE_SIZE];
  strncpy(firstHalf, buffer, index * 12);
  char secondHalf[PageFile::PAGE_SIZE];
  strcpy(secondHalf, &buffer[index * 12]);
  // Place the (key, RecordId) pair at the end of the first half
  strncpy(&firstHalf[index * 12    ], cpid, 4);
  strncpy(&firstHalf[index * 12 + 4], csid, 4);
  strncpy(&firstHalf[index * 12 + 8], ckey, 4);
  // Copy the first half and the second half back into the buffer
  strcpy(buffer, firstHalf);
  strcpy(&buffer[index * 12 + 12], secondHalf);
  // Then return 0
  return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  // This leaf node should be entirely full
  if (getKeyCount() != 85)
    return RC_INVALID_FILE_FORMAT;

  // Get the value of the middle key
  RC rc;
  int middleKey; 
  RecordId middleRid;
  if ((rc = readEntry(43, middleKey, middleRid)) < 0)
    return rc;

  // splitIndex delineates where the buffer should be split apart
  // The insertion needs to occur in the first half or the second half for the
  // nodes to have the mininum number of keys and pointers. If the key is less
  // than the middle key, then the split should occur at 42 so that the
  // insertion can occur in to the first half. The same logic for 43.
  int splitIndex;
  if (key < middleKey)
    splitIndex = 42;
  else
    splitIndex = 43;

  // Seperate the buffer into the first half or the second half delineated by
  // the split index.
  char originalNode[PageFile::PAGE_SIZE];
  char siblingNode[PageFile::PAGE_SIZE];
  strncpy(originalNode, buffer, splitIndex * 12);
  strncpy(siblingNode, &buffer[splitIndex * 12], (85 - splitIndex) * 12);
  
  // Get the original page id
  char originalPageId[4];
  strncpy(originalPageId, &buffer[PageFile::PAGE_SIZE-4], 4);

  // Set the original node
  memset(buffer, 0, PageFile::PAGE_SIZE);
  strcpy(buffer, originalNode);
  // Set the sibling node
  memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
  strcpy(sibling.buffer, siblingNode);

  // Insert the (key, RecordId) pair into the correct node
  if (splitIndex == 42) // Insert the pair into the original
    rc = insert(key, rid);
  else // Insert the pair into the sibling
    rc = sibling.insert(key, rid);
  if (rc < 0)
    return rc;

  // Set the sibling key to the first key in the sibling node */
  RecordId notUsedRid;
  if ((rc = readEntry(1, siblingKey, notUsedRid)) < 0)
    return rc;
  if ((rc = sibling.setNextNodePtr(atoi(originalPageId))) < 0)
    return rc;

  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    char charKey[4];
    strncpy(charKey, &buffer[i], 4);

    // Every non data byte should be null
    if (charKey[0] == '\0')
	{
	  eid = (i - 8) / 12;
	  return RC_NO_SUCH_RECORD;
	}

    int intKey = atoi(charKey);
	
    if (intKey >= searchKey)
    {
      eid = (i - 8) / 12;
      return 0;
    }
  }

  return RC_END_OF_TREE;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
  int index = (eid - 1) * 12;

  char cpid[4];
  char csid[4];
  char ckey[4];

  strncpy(cpid, &buffer[index    ], 4);
  strncpy(csid, &buffer[index + 4], 4);
  strncpy(ckey, &buffer[index + 8], 4);

  // Return error when nothing is found
  if (cpid[0] == '\0' || csid[0] == '\0' || ckey[0] == '\0')
    return RC_NO_SUCH_RECORD;

  rid.pid = atoi(cpid);
  rid.sid = atoi(csid);
  key = atoi(ckey);

  return 0;
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
  char *siblingPid = &buffer[getKeyCount() * 12];
  return atoi(siblingPid);
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
  if(pid < 0)
    return RC_INVALID_PID;

  char *siblingPid = &buffer[getKeyCount() * 12];
  sprintf(siblingPid, "%04d", pid);

  // Check that everything worked
  if(getNextNodePtr() != pid)
    return RC_FILE_WRITE_FAILED;

  return 0;
}

RC BTLeafNode::empty()
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  return 0;
}

//=====================================================================================================

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read(pid, buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
  int keyCount = 0;
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    if (buffer[i] != '\0')
      keyCount++;
    else
      return keyCount;
  }
  return keyCount;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  // Error out if the node is full
  if(getKeyCount() == 85)
    return RC_NODE_FULL;

  // Find the first entry that is equal to or greater than the key
  int index;
  RC rc = locate(key, index);

  // Convert the pid and key into cstrings
  char cpid[5];
  sprintf(cpid, "%04d", pid);
  char ckey[5];
  sprintf(ckey, "%04d", key);
  
  // Insert the key and pid pair at the end
  if (rc == RC_NO_SUCH_RECORD)
  {
    strcpy(&buffer[index * 12    ], cpid);
    strcpy(&buffer[index * 12 + 8], ckey);
    return 0;
  }

  // Insert the key in the middle
  // First split into two where the insertion point should be
  char firstHalf[PageFile::PAGE_SIZE];
  strncpy(firstHalf, buffer, index * 12);
  char secondHalf[PageFile::PAGE_SIZE];
  strcpy(secondHalf, &buffer[index * 12]);
  // Place the (key, RecordId) pair at the end of the first half
  strcpy(&firstHalf[index * 12    ], cpid);
  strcpy(&firstHalf[index * 12 + 8], ckey);
  // Copy the first half and the second half back into the buffer
  strcpy(buffer, firstHalf);
  strcpy(&buffer[index * 12 + 12], secondHalf);
  // Then return 0
  return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{
  // This leaf node should be entirely full
  if (getKeyCount() != 85)
    return RC_INVALID_FILE_FORMAT;

  // Get the value of the middle key
  char charMidKey[4];
  strncpy(charMidKey, &buffer[43*12+8], 4);
  int middleKey = atoi(charMidKey);
  
  // splitIndex delineates where the buffer should be split apart
  // The insertion needs to occur in the first half or the second half for the
  // nodes to have the mininum number of keys and pointers. If the key is less
  // than the middle key, then the split should occur at 42 so that the
  // insertion can occur in to the first half. The same logic for 43.
  int splitIndex;
  if (key < middleKey)
    splitIndex = 42;
  else
    splitIndex = 43;

  // Seperate the buffer into the first half or the second half delineated by
  // the split index.
  char originalNode[PageFile::PAGE_SIZE];
  strncpy(originalNode, buffer, splitIndex * 12);
  char siblingNode[PageFile::PAGE_SIZE];
  strncpy(siblingNode, &buffer[splitIndex * 12], (85 - splitIndex) * 12);
  
  // Get the original page id
  char originalPageId[4];
  strncpy(originalPageId, &buffer[PageFile::PAGE_SIZE-4], 4);

  // Set the original node
  memset(buffer, 0, PageFile::PAGE_SIZE);
  strcpy(buffer, originalNode);
  // Set the sibling node
  memset(sibling.buffer, 0, PageFile::PAGE_SIZE);
  strcpy(sibling.buffer, siblingNode);

  RC rc;
  // Insert the (key, pid) pair into the correct node
  if (splitIndex == 42) // Insert the pair into the original
    rc = insert(key, pid);
  else // Insert the pair into the sibling
    rc = sibling.insert(key, pid);
  if (rc < 0)
    return rc;

  // Set the midkey to the first key in the sibling node */
  char chMidKey[4];
  strncpy(chMidKey, &buffer[8], 4);
  midKey = atoi(charMidKey);

  return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
  int index;
  RC rc;
  if ((rc = locate(searchKey, index)) < 0)
    return rc;

  char charPid[4];
  strncpy(charPid, &buffer[index * 12], 4);
  return atoi(charPid);
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  if(pid1 < 0 || pid2 < 0)
    return RC_INVALID_PID;
  RC rc;
  if ((rc = insert(key, pid1)) < 0)
    return rc;

  char *siblingPid = &buffer[12];
  sprintf(siblingPid, "%04d", pid2);

  return 0;
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locate(int searchKey, int& eid)
{
  for (int i = 8; i < PageFile::PAGE_SIZE; i += 12)
  {
    char charKey[4];
    strncpy(charKey, &buffer[i], 4);

    // Every non data byte should be null
    if (charKey[0] == '\0')
	{
	  eid = (i - 8) / 12;
	  return RC_NO_SUCH_RECORD;
	}

    int intKey = atoi(charKey);
	
    if (intKey >= searchKey)
    {
      eid = (i - 8) / 12;
      return 0;
    }
  }

  return RC_END_OF_TREE;
}

RC BTNonLeafNode::empty()
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  return 0;
}

